package hashmap;

import java.util.*;

public class ThreeSum15 {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums.length < 2)
            return res;
        Arrays.sort(nums);
        HashMap<Integer, Integer> map = new HashMap<>();
        HashSet<List<Integer>> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int fixedFirst = nums[i];
            int target = -fixedFirst;
            for (int j = i + 1; j < nums.length; j++) {
                List<Integer> comb = new ArrayList<>();
                if (i == j)
                    continue;
                if (map.containsKey(target - nums[j]) && map.get(target - nums[j]) != j && map.get(target - nums[j]) != i) {
                    comb.add(fixedFirst);
                    comb.add(target - nums[j]);
                    comb.add(nums[j]);
                    Collections.sort(comb);
                    if (!set.contains(comb))
                        res.add(comb);
                    set.add(comb);
                }
                map.put(nums[j], j);
            }

        }
        return res;
    }
    public static List<List<Integer>> threeSum2(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums.length < 3)
                return res;

            Arrays.sort(nums);//first we sort the array
            for(int i = 0 ; i < nums.length; i++){
                if(nums[i] > 0)
                    return res;
                // if the next value is the same it must
                //have been considered already in previous round so we just skip it
                if(i > 0 && nums[i] == nums[i-1])
                    continue;
                int L = i + 1;
                int R = nums.length - 1;
                while(L < R){
                    if(nums[i] + nums[L] + nums[R] == 0){
                        List<Integer> comb = new ArrayList<>();
                        comb.add(nums[i]);
                        comb.add(nums[L]);
                        comb.add(nums[R]);
                        res.add(comb);
                        //remove duplicates in a similar way
                        //but this time do it at both left and right side
                        //also important is that we need to make sure we do not cross the loop bund
                        while(L < R && nums[L] == nums[L+1]){
                            L ++;
                        }
                        while(L < R && nums[R] == nums[R - 1]){
                            R --;
                        }
                        L++;
                        R--;
                    }else if(nums[i] + nums[L] + nums[R] > 0){
                        R--;
                    }else
                        L++;
                }
            }
            return res;
    }

    public static void main(String[] args) {
        System.out.println(threeSum2(new int[]{1,-1,-1,0}));
    }

}
